package com.mjf.search;

/**
 * 插值查找
 * <p>
 * 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找
 * <p>
 * int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
 * <p>
 * 优点：对于数据量较大，分布比较均匀的查找来说，采用插值查找时速度较快
 * <p>
 * 缺点：分布不均匀的情况下，插值查找不一定比二分查找好
 */
public class InsertValSearch {

    public static void main(String[] args) {

        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }

        int index = insertValSearch(arr, 0, arr.length - 1, 51);  // 方法调用一次
//        int index = binarySearch(arr, 0, arr.length - 1, 51);   // 方法调用6次
        if (index == -1) {
            System.out.println("数据没查到");
        } else {
            System.out.println("数据下标为：" + index);
        }

    }

    /**
     * 插值查找
     */
    public static int insertValSearch(int[] arr, int left, int right, int value) {
        System.out.println("insertValSearch方法被调用~~~");
        // value < arr[0] || value > arr[arr.length - 1]必须要，防止下标越界
        if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        int mid = findVal(arr, left, right, value);
        if (arr[mid] < value) {
            return insertValSearch(arr, left, mid - 1, value);
        } else if (arr[mid] > value) {
            return insertValSearch(arr, mid + 1, right, value);
        } else {
            return mid;
        }
    }

    /**
     * 查到自适应mid
     */
    public static int findVal(int[] arr, int left, int right, int value) {
        return left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
    }

    public static int binarySearch(int[] arr, int left, int right, int value) {
        System.out.println("binarySearch方法被调用~~~");
        if (left > right) {
            return -1;
        }

        // 中间索引
        int mid = (left + right) / 2;

        if (arr[mid] > value) {
            // 中间元素大于待查询元素，向左递归
            return binarySearch(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            // 中间元素小于待查询元素，向右递归
            return binarySearch(arr, mid + 1, right, value);
        } else {
            return mid;
        }
    }

}
